This invention relates generally to computer memory, and more particularly to a scheme for storing data in the memory.
It is generally known that computers have significantly changed since they were first developed. For example, during the early development of the computer, the processor and the memory typically operated at the same speed, more or less. Due to the fact that both the memory and the processor operated at approximately the same speed, the processor did not generally have to wait for the memory to supply it data.
Since this time, the speed of every component (e.g., processor, memory, etc.) of the computer has increased. However, processor speeds have increased relatively faster than memory speeds. This disparity in speed growth has resulted in processors that run significantly faster than the memory. Thus, it is a goal in modem system design, to expediently provide the processor with data for reducing processor waiting time and minimize the wasting of processing cycles. One method of reducing processor latency is to utilize a relatively high speed memory (e.g., static random access memory xe2x80x9cSRAMxe2x80x9d). However, the cost of a sufficient amount of SRAM to provide data storage for current computer applications (e.g., 64 mega bytes xe2x80x9cMBxe2x80x9d) makes this method prohibitive. A second method of reducing processor latency is to place memory in close proximity to the processor or on the same chip as the processor. However, the physical dimensions of the chip limit the amount of memory that can be placed on or around the chip.
In this regard, current computers generally utilize a comparatively small xe2x80x9ccachexe2x80x9d (e.g., 256 kilo bytes xe2x80x9cKBxe2x80x9d, 1 MB and the like) of relatively fast memory located on or near the chip with the processor and a comparatively large amount of system or remote memory. The remote memory is a relatively slower and less expensive memory (e.g., dynamic random access memory xe2x80x9cDRAMxe2x80x9d and the like) located in a remote location (e.g., somewhere on the motherboard, on a daughter board, etc.). Additionally, the cache is typically represented as two or more levels of cache. For example a level 1 (xe2x80x9cL1xe2x80x9d) cache or caches is typically smaller, faster and in closer proximity to the processor than a level 2 (xe2x80x9cL2xe2x80x9d) cache.
The L1 or primary cache is typically the fastest memory available to the processor. It is in fact, built directly into the processor itself and runs at the same speed as the processor in most cases. While fast, the L1 cache is very small, generally from 8 KB to 64 KB. If the processor requests information and can find it in the L1 cache, that is the best case, because the information is there immediately and the system does not have to wait.
The L2 cache is a secondary cache to the L1 cache, and is larger and slower as compared to the L1 cache. In general, the L2 cache is utilized to store data recently accessed by the processor that is not stored in the L1 cache. The size of the L2 cache is typically in the range of 64 KB to 4 MB. Due to the fact that the L1 and the L2 cache are built into or are in relatively close proximity to the processor, the combined memory resources of the L1 and the L2 cache are often referred to as the xe2x80x9clocal memoryxe2x80x9d.
In general, data flows between the various levels of cache in the following manner. The processor requests a piece of information. The first place the processor looks for the information is in the L1 cache. If the information is found in the L1 cache (called an xe2x80x9cL1 hitxe2x80x9d), the information may be utilized by the processor with no performance delay. If the information is not found in the L1, the L2 cache is searched. If the information is found in the L2 cache (called an xe2x80x9cL2 hitxe2x80x9d), the information may be utilized by the processor with relatively little delay. Otherwise, the processor must issue a request to read the information from the remote memory. The remote memory may in turn either have the information available or have to get it from the still slower hard disk or CD-ROM. A caching algorithm is utilized to migrate data required by the processor between the various levels of the cache and also to migrate data between the cache and the remote or xe2x80x9cmainxe2x80x9d memory.
Due to the fact that getting information to the processor has become a limiting factor in computer performance, designing more efficient caching algorithms has become extremely important in improving overall computer performance. Specifically, the hit ratio and the search speed must be maximized to improve the cache performance. The hit ratio is a measure of the likelihood of the cache containing the memory addresses that the processor requires. The search speed is a measure of how quickly it is determined if a hit in the cache has occurred. In this regard, there is a critical tradeoff in cache performance that has led to the creation of a multitude of caching algorithms.
FIG. 4 illustrates a conventional direct mapping caching scheme 400 of one such conventional caching algorithm. The caching scheme 400 illustrated in FIG. 4 depicts the flow of data during a particular data operation. Specifically, the data operation is the replacement of a relatively low priority data with a relatively high priority data. In the caching scheme 400, the processor (not shown) requires a line 405. The processor references a local memory 410 to determine whether the line 405 is present (i.e., a xe2x80x9ctag matchxe2x80x9d) or not present (i.e., a xe2x80x9ctag mismatchxe2x80x9d).
In the caching scheme 400, each line in the local memory 410 is associated with an address 415. Included within the address 415 is a xe2x80x9ctagxe2x80x9d 420 utilized to associate the line in the local memory 410 to a corresponding line in a remote memory 425. The xe2x80x9ctagxe2x80x9d portion 420 of the address 415 is stored with the cache line, while the remaining portion of the address can be derived implicitly by the line""s physical location within the cache. In the example shown, it has been determined that the line 405 is not present in the local memory 410. Thus, the processor must issue a request to retrieve the line 405 from the remote memory 425.
Utilizing the caching scheme 400, a victim line 430 is located within the local memory 410 and replaced with the line 405. In a direct mapped scheme such as that described here, the selection of a victim line is precisely determined by the non-tag portion of its address. In a more general scheme, however, victim lines would be selected based on how likely it is that the line will be utilized by the processor. Typically, the longer the time interval since the line has been utilized, the more likely the line will be chosen as the victim. Prior to replacing the line 430 with the line 405, it is determined if the line 430 contains new information. In this regard, a xe2x80x9cdirtyxe2x80x9d bit 435 is utilized to indicate that the line has been altered since it was retrieved from remote memory 425. Thus, if the dirty bit 435 of the line 430 is turned on, the line 430 most be written back to the corresponding location in the remote memory 425 in order to avoid losing the new information stored to the line 430.
While the conventional caching scheme 400 has the advantage of being relatively simple and having a relatively fast search speed, the caching scheme 400 suffers a number of disadvantages. For example, read and write requests are processed individually rather than as a batch or xe2x80x9cburstxe2x80x9d process. A second disadvantage of the caching scheme 400 is the overhead caused by the address tag 420. For example, in a 64-bit processor, a 4 MB direct mapped cache of 32 byte lines may have an address tag of 42 bits for every 32 byte line. This equates to 16.4 percent memory usage for address tags.
In an effort to improve upon conventional direct mapping scheme for relatively large L2 memories, a demand paging caching scheme was developed. In the demand paging scheme, a plurality of lines are moved into the cache rather than individual lines in the direct mapping scheme. The plurality of lines are collectively described by those skilled in the art as a xe2x80x9cpagexe2x80x9d of data. In this manner, an address tag may reference a page and thus, each line has a reduced memory overhead.
FIGS. 5A to 5D collectively illustrate a conventional demand paging caching scheme 500. Each page has a unique virtual page number by which CPU 501 refers to that page. In addition, each memory page has a unique physical page number in remote memory. Furthermore, if the page happens to be cached in local memory, it will have a local physical page number. Page table 510 maintains complete virtual-to-physical mappings for all memory pages. In addition, a translation lookaside buffer (xe2x80x9cTLBxe2x80x9d) 505 caches some, but not necessarily all, virtual-to-local-physical-page-number mappings. In FIG. 5A, a processor 501 requires a line ffffc010 within a virtual page ffffc. In an attempt to find the virtual page ffffc, the processor 501 queries a translation lookaside buffer (xe2x80x9cTLBxe2x80x9d) 505. The TLB 505 maintains an associative table of virtual page addresses and their corresponding local physical page addresses for a local memory 515 (shown in FIG. 5B). In response to not finding the virtual page ffffc within the local memory 515, a page fault is generated.
In response to the page fault, a victim page mapping is selected from the TLB 505 and a victim local page is identified by consulting page table 510. The page table 510 maintains an associative table of virtual page addresses and their corresponding local and remote physical addresses. As depicted in FIG. 5A, the victim page mapping for the TLB 505 is the 0703c/0002 mapping, and page table 510 has been used to select a victim page with local physical address 10040.
As shown in FIG. 5B, in response to a dirty bit 525 for the page 10040 being turned xe2x80x9conxe2x80x9d, the information contained in the page 10040 of the local memory 515 is re-written to its corresponding remote memory 520 page location. The dirty bit 525, in a manner similar to the dirty bit described in FIG. 4, is utilized to identify that information within the page 10040 has been modified. However, regardless of the number of modified lines within the page, the entire page 10040 is re-written.
As shown in FIG. 5C, the dirty bit 525 is turned xe2x80x9coffxe2x80x9d and the contents of the remote physical page 11008 (also known as the virtual page ffffc) are migrated into the local memory 515.
As shown in FIG. 5D, the TLB 505 and the page table 510 are updated as required.
While demand paging scheme improves the ability to batch process read and write processes and decreases the memory overhead as compared to direct mapping caching scheme, demand paging scheme has a number of disadvantages. For example, one particular disadvantage in demand paging is that if one line in a page has a dirty bit turned on, the entire page is written back to memory. A second disadvantage is that when a single line is required by the processor, an entire page is moved to cache, regardless of how many other lines from that page are required by the processor.
In one respect, the invention pertains to a method of writing back a dirty page from a local memory to a remote memory. In this method, a plurality of memory pages are stored in the local memory. Each page contains a plurality of memory lines. Further, it is determined in this method whether one or more lines of a page of the plurality of pages in the local memory are dirty. Additionally, in this method, only the one or more dirty lines of the dirty page are written back to the remote memory.
In another respect, the invention relates to a method of writing data to a local memory from a remote memory. In this method, a request for a line of data associated with a page of data is received and it is determined whether the page of data is in the local memory. A victim page is selected in the local memory in response to the page of data not being in the local memory and it is determined whether one or more lines of the victim page are dirty. Only the one or more dirty lines are written to the remote memory in response to determining that one or more lines are dirty. The requested line of data is fetched from the remote memory and the requested line of data is stored in the local memory within the page of data at a location previously occupied by the victim page.
In yet another respect, the invention pertains to a computer readable medium on which is embedded computer software, the software comprising executable code for performing a method of writing back a dirty page from a local memory to a remote memory. In this method, a plurality of memory pages are stored in the local memory. Each page contains a plurality of memory lines. Further, it is determined in this method whether one or more lines of a page of the plurality of pages in the local memory are dirty. Additionally, in this method, only the one or more dirty lines of the dirty page are written back to the remote memory.
In yet another respect, the invention relates to a computer readable medium on which is embedded computer software, the software comprising executable code for performing a method of writing data to a local memory from a remote memory. In this method, a request for a line of data associated with a page of data is received and it is determined whether the page of data is in the local memory. A victim page is selected in the local memory in response to the page of data not being in the local memory and it is determined whether one or more lines of the victim page are dirty. Only the one or more dirty lines are written to the remote memory in response to determining that one or more lines are dirty. The requested line of data is fetched from the remote memory and the requested line of data is stored in the local memory within the page of data at a location previously occupied by the victim page.
In yet another respect, the invention pertains to an apparatus for storing data in a memory. The apparatus includes a processor and a remote memory. The apparatus further includes a local memory configured to store a page of data. The page of data includes a plurality of lines of data. Each line of data has a respective valid bit and dirty bit. The respective valid bit is utilized to indicate data stored by the corresponding line of data has been fetched from the remote memory. The respective dirty bit is utilized to indicate data stored by the corresponding line of data has been modified by the processor. The apparatus further includes a bus configured to interconnect the processor, the remote memory and the local memory.
In yet another respect, the invention relates to a method of writing data to a local memory from a remote memory. In this method, a request for a line of data associated with a page of data is received and it is determined whether the page of data is in the local memory. Further, in response to the page of data being in the local memory, it is determined whether the requested line of data is in the local memory. Additionally, in response to the requested line of data not being in the local memory, only the requested line of data is fetched from the remote memory and stored within the page of data. Moreover, a valid bit is set for the requested line of data stored within the page of data.
In yet another respect, the invention pertains to a method for storing data in memory. In this method, a request for a line of data associated with a page of data is received and it is determined whether the page of data is in a local memory. A victim page is selected in the local memory in response to the page of data not being in the local memory and it is determined whether one or more lines of the victim page are dirty. In response to determining that one or more lines of the victim page are dirty only the one or more dirty lines of the victim page are written to a remote memory. Further, in response to selecting the victim page, it is determined whether one or more lines of the victim page are valid. In response to determining one or more lines of the victim page are valid, the one or more valid bits associated with the victim page are cleared. Additionally, the requested line of data is fetched from the remote memory and stored within the page of data at a location previously occupied by the victim page. Moreover, a valid bit associated with the requested line is set and a page table and a translation lookaside buffer are updated with data associated with storing the requested line of data within the page of data at a location previously occupied by the victim page.
In yet another respect, the invention relates to an apparatus for writing back a dirty page from a local memory to a remote memory. The apparatus includes a means for storing a plurality of memory pages in the local memory. Each of the plurality of memory pages contains a plurality of memory lines. The apparatus further includes a means for determining whether one or more lines of a page of the plurality of pages in the local memory are dirty; and a means for writing back only the one or more dirty lines of the page to the remote memory.
In yet another respect, the invention pertains to an apparatus for writing data to a local memory from a remote memory. The apparatus includes a means for receiving a request for a line of data. The line of data being associated with a page of data. The apparatus further includes a means for determining whether the page of data is in the local memory and a means for selecting a victim page in the local memory in response to the page of data not being in the local memory. Additionally, the apparatus includes a means for determining whether one or more lines of the victim page are dirty and a means for writing only the one or more dirty lines of the victim page to the remote memory in response to determining that one or more lines of the victim page are dirty. Furthermore, the apparatus includes a means for fetching the requested line of data from the remote memory and a means for storing the requested line of data in the local memory within a location previously occupied by the victim page.
In yet another respect, the invention relates to an apparatus for writing data to a local memory from a remote memory. The apparatus includes a means for receiving a request for a line of data. The line of data is associated with a page of data. The apparatus further includes a means for determining whether the page of data is in the local memory and a means for determining whether the requested line of data is in the local memory in response to the page of data being in the local memory. Additionally, the apparatus includes a means for fetching only the requested line of data from the remote memory in response to the requested line of data not being in the local memory. Moreover, the apparatus includes a means for storing only the requested line of data within the page of data and a means for setting a valid bit for the requested line of data stored within the page of data.
In yet another respect, the invention pertains to an apparatus for storing data to memory. The apparatus includes a means for receiving a request for a line of data. The line of data is associated with a page of data. The apparatus further includes a means for determining whether the page of data is in a local memory and a means for selecting a victim page in the local memory in response to the page of data not being in the local memory. Additionally, the apparatus includes a means for determining whether one or more lines of the victim page are dirty, a means for writing only the one or more dirty lines of the victim page to a remote memory in response to determining that one or more lines of the victim page are dirty, and a means for determining whether one or more lines of the victim page are valid in response to selecting the victim page. Furthermore, the apparatus includes a means for clearing the one or more valid bits associated with the victim page in response to determining one or more lines of the victim page are valid, a means for fetching the requested line of data from the remote memory and a means for storing the requested line of data within the page of data at a location previously occupied by the victim page. Moreover, the apparatus includes a means for setting a valid bit associated with the requested line, a means for updating a page table with data associated with storing the requested line of data within the page of data at a location previously occupied by the victim page and a means for updating a translation lookaside buffer with data associated with storing the requested line of data within the page of data at a location previously occupied by the victim page.